/**
 * @file 198.HouseRobber.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-26
 * 
 * @copyright Copyright (c) 2021
 * 
 * 198.打家劫舍I        -- 普通打劫，隔一家打劫一次
 * 213.打家劫舍II       -- 环形打劫，首尾不能同时打劫
 * 337.打家劫舍III      -- 树形打劫，不能同时打劫直接相连节点（父亲和儿子）
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : val(val), left(left), right(right) {}
};

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    cout << '[';
    while (it != Containers.end()) {
        cout << *it << ", ";
        ++it;
    }
    cout << ']';
    cout << endl;
}

class Solution
{
public:
    // 打家劫舍I
    // 隔一家打劫，要求金额最大
    int robI(vector<int> &nums)
    {
        // dp[i] 以nums[i]结尾所得最大金额
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }
    // 打家劫舍II
    // 数组成环，不能同时打劫首尾元素
    int robII(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }
        vector<int> dp(n, 0);
        int res1 = robRange(nums, 0, n - 2);
        int res2 = robRange(nums, 1, n - 1);
        return max(res1, res2);
    }

private:
    int robRange(vector<int> &nums, int left, int right)
    {
        if (left == right) {
            return nums[left];
        }
        vector<int> dp(nums.size(), 0);
        dp[left] = nums[left];
        dp[left + 1] = max(nums[left], nums[left + 1]);
        for (int i = left + 2; i <= right; ++i) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[right];
    }

public:
    int robIII(TreeNode *root)
    {
        vector<int> res = traversal(root);
        return max(res[0], res[1]);
    }

private:
    // 当前节点不抢/抢 所得最高金额
    // 返回值：[不抢所得，抢所得]
    vector<int> traversal(TreeNode *root)
    {
        if (!root) {
            return {0, 0};
        }
        vector<int> left = traversal(root->left);
        vector<int> right = traversal(root->right);
        // 抢当前节点，那么两个儿子节点就不能抢
        int rob = root->val + left[0] + right[0];
        // 不抢当前节点，两个儿子抢还是不抢，就得取个最大值
        int noRob = max(left[0], left[1]) + max(right[0], right[1]);
        return {noRob, rob};
    }
};

void test198()
{
    vector<int> nums1 = {1, 2, 3, 1};
    vector<int> nums2 = {2, 7, 9, 3, 1};
    cout << Solution().robI(nums1) << endl;
    cout << Solution().robI(nums2) << endl;
}

void test213()
{
    vector<int> nums1 = {2, 3, 2};
    vector<int> nums2 = {1, 2, 3, 1};
    cout << Solution().robII(nums1) << endl;
    cout << Solution().robII(nums2) << endl;
}

int main()
{
    // test198();
    test213();
    return 0;
}